package algorithm_demo.demo_advanced;

/**
 * 并行算法（岛屿问题只是一种启发性的说明）
 *
 * @author Api
 * @date 2023/4/5 19:26
 */
public class Code17_Islands {
    /*
    * 岛问题
    * 一个只有0和1两种数字的二维矩阵中，
    * 上下左右能连成一片的1，算一个岛屿，返回矩阵中，一共有几个岛
    * */

    public static int countIslands1(int[][] m){
        if (m == null || m[0] == null){
            return 0;
        }
        int N = m.length;
        int M = m[0].length;
        int res = 0;
        for(int i = 0; i< N; i++){
            for(int j = 0; j < M; j++){
                if (m[i][j] == 1){
                    res++;
                    infect(m, i, j, N, M);
                }
            }
        }
        return res;
    }
    public static void infect(int[][] m, int i, int j, int N, int M){
        if (i < 0 || i>=N || j<0||j>=M || m[i][j] != 1){
            return;
        }
        m[i][j] = 2;
        infect(m, i+1, j, N,M);
        infect(m, i-1, j, N,M);
        infect(m, i, j+1, N,M);
        infect(m, i, j-1, N,M);
    }
    /*
    *
    * https://leetcode.cn/problems/number-of-islands/
    *
    * 给你一个由'1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
    * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
    * 此外，你可以假设该网格的四条边均被水包围。
    *
    * */
    public int numIslands(char[][] grid) {
        if(grid == null || grid[0] == null){
            return 0;
        }
        int N = grid.length;
        int M = grid[0].length;
        int res = 0;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                if(grid[i][j] == '1'){
                    res++;
                    infect(grid, i, j, N, M);
                }
            }
        }
        return res;
    }

    public static void infect(char[][] grid, int i, int j, int N, int M){
        if(i < 0 || i >= N || j < 0 || j >= M || grid[i][j] != '1'){
            return;
        }
        grid[i][j] = '2';
        infect(grid, i+1, j, N, M);
        infect(grid, i-1, j, N, M);
        infect(grid, i, j+1, N, M);
        infect(grid, i, j-1, N, M);
    }
}
